import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    class DLNode {
        public int key;
        public int val;
        public DLNode prev;
        public DLNode next;
        public DLNode() {}
        public DLNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    DLNode head;
    DLNode tail;
    Map<Integer, DLNode> cache;
    int size;
    int capacity;

    public LRUCache(int capacity) {
        head = new DLNode();
        tail = new DLNode();
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.capacity = capacity;
        cache = new HashMap<>();
    }

    // 当调用get方法的时候需要将这个node放在head
    public int get(int key) {
        DLNode node = cache.get(key);
        if (node == null) {
            return -1;
        } else {
            // 先将当前节点删除掉，然后在将其添加到head节点之后
            removeNode(node);
            moveToHead(node);
        }
        return node.val;
    }

    public void put(int key, int value) {
        // 先判断当前key是否存在，如果存在则直接替换节点的值，然后将其移动到head节点之后
        // 如果不存在，则创建出一个新的节点并且将其添加在head节点之后，添加完成之后需要判断元素
        // 的个数是否超过了capacity，如果超过了则移除最久未使用的节点
        DLNode node = cache.get(key);
        if (node != null) {
            // 更新节点的值
            node.val = value;
            // 将当前节点移动到head节点之后
            removeNode(node);
            moveToHead(node);
        } else {
            node = new DLNode(key, value);
            cache.put(key, node);
            moveToHead(node);
            // 添加新的节点之后需要判断当前容量是否大于最大容量
            this.size++;
            if (this.size > this.capacity) {
                cache.remove(tail.prev.key);
                removeNode(tail.prev);
                this.size--;
            }
        }

    }

    private void moveToHead(DLNode node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void removeNode(DLNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}
